#include <bits/stdc++.h>
using namespace std;

/*
2654. 使数组所有元素变成 1 的最少操作次数
已解答
中等
相关标签
premium lock icon
相关企业
提示
给你一个下标从 0 开始的 正 整数数组 nums 。你可以对数组执行以下操作 任意 次：

选择一个满足 0 <= i < n - 1 的下标 i ，将 nums[i] 或者 nums[i+1] 两者之一替换成它们的最大公约数。
请你返回使数组 nums 中所有元素都等于 1 的 最少 操作次数。如果无法让数组全部变成 1 ，请你返回 -1 。

两个正整数的最大公约数指的是能整除这两个数的最大正整数。

 

示例 1：

输入：nums = [2,6,3,4]
输出：4
解释：我们可以执行以下操作：
- 选择下标 i = 2 ，将 nums[2] 替换为 gcd(3,4) = 1 ，得到 nums = [2,6,1,4] 。
- 选择下标 i = 1 ，将 nums[1] 替换为 gcd(6,1) = 1 ，得到 nums = [2,1,1,4] 。
- 选择下标 i = 0 ，将 nums[0] 替换为 gcd(2,1) = 1 ，得到 nums = [1,1,1,4] 。
- 选择下标 i = 2 ，将 nums[3] 替换为 gcd(1,4) = 1 ，得到 nums = [1,1,1,1] 。
示例 2：

输入：nums = [2,10,6,14]
输出：-1
解释：无法将所有元素都变成 1 。
 

提示：

2 <= nums.length <= 50
1 <= nums[i] <= 106
*/

// 法一
class Solution {
public:
    // helper
    int gcd(int a, int b) {
        while (b != 0) {
            int tmp = b;
            b = a % b;
            a = tmp;
        }
        return a;
    }

    int minOperations(vector<int>& nums) {
        // gcd 
        int n = nums.size();
        int cnt_1 = 0;
        for (int num : nums) {
            if (num == 1) cnt_1++;
        }
        // 总长度 = len - cnt_1
        if (cnt_1 > 0)  return n - cnt_1;

        // 最短的 gcd = 1
        int min_len = INT_MAX;
        for (int i = 0; i < n; i++) {
            int cur_gcd = nums[i];
            for (int j = i; j < n; j++) {
                // 贪心思想 逐步更新
                cur_gcd = gcd(cur_gcd, nums[j]);
                if (cur_gcd == 1) {
                    int len = j - i + 1; // 当前子数组长度
                    min_len = min(min_len, len); // 更新最短长度
                    if (min_len == 2)   goto end_find;  // 提前exit
                    break;
                }
            }
        }
    end_find:
        // 无任何子数组GCD为1，无法生成1，返回-1
        if (min_len == INT_MAX) return -1;

        // total
        // 生成1：长度为min_len的子数组需min_len-1次操作（逐步合并相邻元素求GCD）
        // 扩散1：生成1后，剩余n-1个元素各需1次操作变成1
        return (min_len - 1) + (n - 1);
    }
};

